Communication of data over computer networks, particularly the Internet, has become an important, if not essential, way for many organizations and individuals to disseminate information. The Internet is a global network connecting millions of computers using a client-server architecture in which any computer connected to the Internet can potentially receive data from and send data to any other computer connected to the Internet. The Internet provides a variety of methods by which to communicate data, one of the most ubiquitous of which is the World Wide Web. Other methods for communicating data over the Internet include e-mail, usenet newsgroups, telnet and FTP.
The World Wide Web is a system of Internet servers, typically called “web servers”, that support the documents and applications present on the World Wide Web. Documents, known as web pages, may be transferred across the Internet according to the Hypertext Transfer Protocol (“HTTP”) while applications may be run by a Java virtual machine present in an internet browser. Web pages are often organized into web sites that represent a site or location on the world wide web. Web pages and applications can provide a variety of content, including text, graphics, interactive gaming and audio and video content and can link to one or more web pages, files, or applications at the same web site or at other web sites. A user can access web pages using a browser program and can “click on” links in the web pages being viewed to access other web pages.
Because web pages and associated applications can display content and receive information from users, web sites have become popular for enabling commercial transactions. As web sites become more important to commerce, businesses are increasingly interested in quickly providing responses to user's requests. One way of accelerating responses to requests on a web site is to cache the web pages or applications delivered to the requesting user in order to allow faster access time to this content when it is next requested.
Over time, some information in the cache becomes stale. To keep the cache current, information in the cache is periodically removed. Several schemes have been developed to determine which items should be expunged from the cache. Least recently used (LRU) methods discard the least recently used items first. Least frequently used (LFU) methods count how often an item has been accessed over a time period and discard the least frequently used items first. LFU methods tend to give better results for web site caches.
One problem with implementing an LFU policy for file system-based caches is related to performance. LFU caches maintain a reference count in a file associated with each entry. Creating, reading, and updating this reference count require many file I/O operations which are resource expensive. If the cache is large, LFU policies can lead to decreased performance.
Another problem with LFU caches is “cache pollution” in which items that were accessed many times in a short period of time remain in cache. Say, for example, a particular web page representing a breaking news story is stored in a disk cache. This entry may see a great deal of access over a short period of time and then little or no access thereafter. In this case, its high reference count is not a very good indication of its probability of being accessed in the near future, and it might be better to allow the news story to be evicted.
To deal with cache pollution, a common policy variant known as LFU-Aging is employed. From time to time all reference counts in the system are reduced. The effect is that over time earlier accesses are weighted less heavily in the reference count than more recent accesses. Again, however there are potential performance issues because of the many file I/O operations required to read and update the reference counts.